Demand-driven Incrementalization
It it often a good idea to avoid redoing expensive computations. As a first approach, we can cache the result of a function call with a certain value, so that we can just return the cached results when the function is called with the same value again. However, when the input changes, then, no matter how small the change, it seems that we would need to perform the entire computation from scratch. The field of incremental computation studies how we can construct programs that reuse already computed results when the data changes. For example, when changing a cell in an Excel sheet, only the cells depending on it are recomputed.
In this seminar topic, you will study Adapton, a library bringing the benefits of incremental programming to a wider class of programs. You will:
- Explain how Adapton is used with a concrete code example,
- Describe how Adapton tracks dependencies between parts of the computation and
- how it decides when recomputation is needed,
- Sketch how the concept of demand-driven computation is formalized,
- discuss what the benefits and limitations of this approach are,
- compare other approaches to incremental programming in the literature.
You will also write a small program demonstrating your understanding, by either
- using Adapton or a similar library to implement a use case,
- or reimplementing the core of Adapton.